package com.monkeyboy.array;

/**
 * 数组去重
 * 题目：
 * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，
 * 但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 *
 * 要求时间复杂度为O(N)，空间复杂度为O(1)
 *
 * @Author Gavin
 * @date 2021.03.29 09:35
 */
public class ArraysDeDuplication {
    public int duplication(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[i]==nums[nums[i]]){//如果数组的值和数组值下标对应的数组的值相等了说明就有重复的元素了
                    return  nums[i];
                }
                swap(nums, i, nums[i]);//就是把下标i和下标i里面的值进行交换
            }
        }
        return -1;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        ArraysDeDuplication arraysDeDuplication=new ArraysDeDuplication();
        int[] nums={2,3,1,0,2,5};
        int duplication = arraysDeDuplication.duplication(nums);
        System.out.println(duplication);
    }
}
